# Copyright (c) 2009 Peter Corbett
#
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.

import math
import cPickle
import time
import collections

class RayPoint:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.next = []

class LOS:

    matrices = (
	((1, 0), (0, 1)),
	((1, 0), (0, -1)),
	((-1, 0), (0, 1)),
	((-1, 0), (0, -1)),
	((0, 1), (1, 0)),
	((0, 1), (-1, 0)),
	((0, -1), (1, 0)),
	((0, -1), (-1, 0)))

    def __init__(self):
        self.root_raypoint = (0,0,[])
        gradients = []
        for x in range(1, 80):
            for y in range(1, min(x+1, 20)):
                gradient = (y - 0.5) / (x - 0.5)
                gradients.append(gradient)
        gradients.sort()
        #for i in gradients: print i
        lastgradient = -1
        for gradient in gradients:
            if gradient == lastgradient: continue
            lastgradient = gradient
            #if i % 100 == 0: print i
            rp = self.root_raypoint
            #gradient = math.tan(math.radians(i * 45 / 3000.0))
            x = 0.5
            y = 0.5
            xi = 0
            yi = 0
            #report = False
            #if gradient < 0.2501 and gradient > 0.2499:
            #    report = True
            #    print gradient
            while xi < 80:
                xgap = xi+1 - x
                ygap = yi+1 - y
                #if report: print xgap - (ygap / gradient)
                if abs(xgap - (ygap / gradient)) < 1.0e-5:
                    #print "Through"
                    xi += 1
                    yi += 1
                    x = float(xi)
                    y = float(yi)
                elif xgap > ygap / gradient:
                    yi += 1
                    y = float(yi)
                    x += ygap / gradient
                else:
                    xi += 1
                    x = float(xi)
                    y += xgap * gradient
                nrp = None
                for pnrp in rp[2]:
                    if pnrp[0] == xi and pnrp[1] == yi:
                        nrp = pnrp
                        break
                if nrp == None:
                    nrp = (xi, yi, [])
                    rp[2].append(nrp)
                rp = nrp

    def losmap(self, level, data, x, y):
        los_map = [[False for j in range(20)] for i in range(80)]
        for m in self.matrices:
            rps = collections.deque()
            rps.append(self.root_raypoint)
            while len(rps) > 0:
                rp = rps.pop()
                rx = x + (m[0][0] * rp[0]) + (m[0][1] * rp[1])
                ry = y + (m[1][0] * rp[0]) + (m[1][1] * rp[1])
                if not (rx < 0 or ry < 0 or rx >= 80 or ry >= 20):
                    los_map[rx][ry] = True
                    if data.floortiles[level.floortiles[rx][ry]].passable:
                        rps.extend(rp[2])
        return los_map

#	public boolean [][] losMap(Level l, int x, int y) {
#		long time = System.currentTimeMillis();
#		
#		boolean [][] losMap = new boolean[Constants.levelWidth][Constants.levelHeight];
#		for(int i=0;i<Constants.levelWidth;i++) {
#			for(int j=0;j<Constants.levelHeight;j++) {
#				losMap[i][j] = false;
#			}
#		}
#		for(int m = 0;m<matrices.length;m++) {
#			Stack<RayPoint> rps = new Stack<RayPoint>();
#			rps.add(rootRayPoint);
#			while(rps.size() > 0) {
#				RayPoint rp = rps.pop();
#				int rx = x + matrices[m][0][0] * rp.x + matrices[m][0][1] * rp.y;
#				int ry = y + matrices[m][1][0] * rp.x + matrices[m][1][1] * rp.y;
#				if(rx < 0 || ry < 0 || rx >= Constants.levelWidth || ry >= Constants.levelHeight) {
#					
#				} else {
#					losMap[rx][ry] = true;
#					if(Constants.tiles.getTile(l.floortiles[rx][ry]).isPassable()) {
#						rps.addAll(rp.next);
#					}
#				}
#			}
#			
#		}
#		//System.out.println("lostime: " + (System.currentTimeMillis() - time));
#		return losMap;
#	}
def get_los():
    return cPickle.load(open("los.dat", "r"))

#if __name__=="__main__":
    #c = time.clock()
    #l = LOS()
    #print time.clock() - c
    #c = time.clock()
    #f = open("los.dat", "w")
    #cPickle.dump(l, f)
    #f.close()
    #print time.clock() - c
    #c = time.clock()
    #ll = cPickle.load(open("los.dat", "r"))
    #print time.clock() - c
